# 2024.07.23力扣网刷题
# 合并两个有序数组——数组、双指针、排序——简单
# 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
# 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
# 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
# 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
# 示例 1：
# 输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
# 输出：[1, 2, 2, 3, 5, 6]
# 解释：需要合并[1, 2, 3] 和[2, 5, 6] 。
# 合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为 nums1 中的元素。
# 示例 2：
# 输入：nums1 = [1], m = 1, nums2 = [], n = 0
# 输出：[1]
# 解释：需要合并[1] 和[] 。
# 合并结果是[1] 。
# 示例 3：
# 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
# 输出：[1]
# 解释：需要合并的数组是[] 和[1] 。
# 合并结果是[1] 。
# 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
# 提示：
# nums1.length == m + n
# nums2.length == n
# 0 <= m, n <= 200
# 1 <= m + n <= 200
# - 10^9 <= nums1[i], nums2[j] <= 10^9
# 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

class Solution1(object):
    def merge1(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        i = m
        for j in range(n):
            nums1[i] = nums2[j]
            i += 1
        nums1.sort()


    def merge2(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        # 归并排序
        tmp = []
        i, j = 0, 0
        while i < m and j < n:
            if nums1[i] <= nums2[j]:
                tmp.append(nums1[i])
                i += 1
            else:
                tmp.append(nums2[j])
                j += 1
        while i < m:
            tmp.append(nums1[i])
            i += 1
        while j < n:
            tmp.append(nums2[j])
            j += 1
        for i in range(len(tmp)):
            nums1[i] = tmp[i]
        print(tmp)

    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        # 归并排序
        i = m - 1
        j = n - 1
        len = m + n - 1
        while i >= 0 and j >= 0:
            if nums1[i] <= nums2[j]:
                nums1[len] = nums2[j]
                j -= 1
            else:
                nums1[len] = nums1[i]
                i -= 1
            len -= 1
        while j >= 0:
            nums1[len] = nums2[j]
            len -= 1
            j -= 1

# 第三大的数——数组、排序——简单
# 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
# 示例 1：
# 输入：[3, 2, 1]
# 输出：1
# 解释：第三大的数是 1 。
# 示例 2：
# 输入：[1, 2]
# 输出：2
# 解释：第三大的数不存在, 所以返回最大的数 2 。
# 示例 3：
# 输入：[2, 2, 3, 1]
# 输出：1
# 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
# 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
# 提示：
# 1 <= nums.length <= 10^4
# - 2^31 <= nums[i] <= 2^31 - 1
# 进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one = list(set(nums))
        one.sort(reverse=True)
        if len(one) < 3:
            return max(one)
        return one[2]


nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [4,5,6]
n = 3
Solution().merge(nums1, m, nums2, n)
print(nums1)

